/*
 * @lc app=leetcode.cn id=239 lang=c
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *maxSlidingWindow(int *nums, int numsSize, int k, int *returnSize)
{
    int i, left = 0, right = 0;
    int count = 0;
    int *indexes = malloc(numsSize * sizeof(int));
    int *results = malloc((numsSize - k + 1) * sizeof(int));

    for (i = 0; i < numsSize; i++)
    {
        while (right > left && nums[i] >= nums[indexes[right - 1]])
        {
            // 挤出之前较小的
            right--;
        }

        // 记录当前滑动窗口最大值的坐标
        indexes[right++] = i;

        if (i >= k - 1)
        {
            results[count++] = nums[indexes[left]];
        }
        if (i - k + 1 >= indexes[left])
        {
            // left和i分别作为滑动窗口的左右界限
            left++;
        }
    }
    *returnSize = count;
    return results;
}
// @lc code=end
